package com.ftx.service.algorithm.array;

/**
 * Created by tangwenru on 2022/6/19.
 */
public class ArrayTraverse {

    /**
     * 动态规划
     */
    public int maxSubArray(int[] nums) {
        //f(n) = max(f(n-1) + nums[n], nums[n]);
        // 前置的和
        int preSum = 0;

        // 最大值，所有的前置和的最大值。
        int max = nums[0];

        for (int num : nums) {
            preSum = Math.max(preSum + num, num);
            max = Math.max(max, preSum);
        }
        return max;
    }


    public static void main(String[] args) {
        ArrayTraverse arrayTraverse = new ArrayTraverse();
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int result = arrayTraverse.maxSubArray(nums);
        System.out.println(result);
    }

    public int maxSubArray2(int[] nums) {
        int len = nums.length;
        // dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和
        int[] dp = new int[len];
        dp[0] = nums[0];

        for (int i = 1; i < len; i++) {
            //当前数加上一个大于0的数，肯定是大于当前数，否则就等于当前数
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }

        // 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择
        int res = dp[0];
        for (int i = 1; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    //    分治法
    public int maxSubArray3(int[] nums) {
        int len = nums.length;
        return maxSubArraySum(nums, 0, len-1);
    }

//- 第 1 部分：子区间 [left, mid]；
//- 第 2 部分：子区间 [mid + 1, right]；
//- 第 3 部分：包含子区间 [mid , mid + 1] 的子区间，即 nums[mid] 与 nums[mid + 1] 一定会被选取。
    //最大子数组和
    private int maxSubArraySum(int[] nums, int left, int right) {

        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        //
        return Math.max(maxSubArraySum(nums, left, mid),
                Math.max(maxSubArraySum(nums, left + 1, right),
                        maxCrossingSum(nums, left, mid, right)));
    }

    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // 一定会包含 nums[mid] 这个元素
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;
        // 左半边包含 nums[mid] 元素，最多可以到什么地方
        // 走到最边界，看看最值是什么
        // 计算以 mid 结尾的最大的子数组的和
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }
        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        // 右半边不包含 nums[mid] 元素，最多可以到什么地方
        // 计算以 mid+1 开始的最大的子数组的和
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }

}
